public class Solution1392 {
    public String longestPrefix(String s) {
        int[] f=new int[s.length()];
        for (int i=1,j=0;i<s.length();i++){
            while (j>0 && s.charAt(i)!=s.charAt(j)){
                j=f[j-1];
            }
            if (s.charAt(i)==s.charAt(j)){
                j++;
            }
            f[i]=j;
        }
        int m=f[s.length()-1];
        return s.substring(0,m);
    }

    public static void main(String[] args) {
        System.out.println(new Solution1392().longestPrefix("level"));
    }
}
